package com.simon.study.algorithm.zheda;

import com.simon.study.algorithm.tree.Node.LNode;
import java.util.StringJoiner;
import lombok.Getter;

/**
 * <p>
 *
 * @author simon
 */
public class ZLinkList {

    @Getter
    int size;

    LNode first;
    LNode last;


    public ZLinkList() {}


    LNode find(int item){
        LNode tmp = first;
        for(; tmp!= null && tmp.getData() != item; tmp = tmp.getNext());
        return tmp;
    }

    LNode previous(int item){
        LNode tmp = first, prev = null;
        for(; tmp!= null && tmp.getData() != item; tmp = tmp.getNext()){
            prev = tmp;
        }
        return prev;
    }


    LNode findkth(int k){
        int i = 0; LNode tmp = first;
        for(; tmp != null && i < k; tmp = tmp.getNext()){
            i++;
        }

        if( i == k ){ return tmp; }

        return null;
    }


    public boolean insert(int item){
        return insert(size, item);
    }

    public boolean insert(int i, int item){
        if(i < 0 || i > size){ return false; }

        LNode node = new LNode(item);
        if(i == 0){
            first   = node;
        }else if(i==size){
            last.setNext(node);
        }else{
            LNode prev = findkth(i-1);
            node.setNext(prev.getNext());
            prev.setNext(node);
        }

        if(i==size++){ last = node; }
        return true;
    }

    public boolean delete(int i){
        if(i < 0 || i >= size){ return false; }

        LNode node = null;
        if(i==0){
            first = first.getNext();
        }else{
            node            = findkth(i-1);
            node.setNext(node.getNext().getNext());
        }

        if(i==--size){ last = node; }
        return true;
    }

    public static void main(String[] args) {
        ZLinkList list = new ZLinkList();
        System.out.println(list.findkth(2));
        System.out.println(list.find(13));

        int[] arr = {13,1,45,7,20,4,19,13,40,33,38};

        for (int i = 0; i < arr.length; i++) {
            list.insert(arr[i]);
        }
        System.out.println(list.toString());

        System.out.println(list.findkth(3));
        System.out.println(list.toString());

        System.out.println(list.find(7));
        System.out.println(list.toString());


        System.out.println(list.insert(4, 18));
        System.out.println(list.toString());

        System.out.println(list.findkth(4));
        System.out.println(list.toString());

        System.out.println(list.delete(0));
        System.out.println(list.toString());

        System.out.println(list.delete(4));
        System.out.println(list.toString());

        System.out.println(list.delete(list.getSize()-1));
        System.out.println(list.toString());
    }

    public String toString(){
        StringJoiner joiner = new StringJoiner(",");
        for(LNode tmp = first; tmp != null; tmp = tmp.getNext()){
            joiner.add(tmp.getData().toString());
        }
        return joiner.toString();
    }
}
